Skip to main content

第27章 模拟算法

模拟算法(Simulation Algorithm)是一种通过模仿现实问题的运行过程或操作步骤来求解问题的算法。它照问题所描述的规则或流程，一步一步地进行计算和操作，最终得到问题的结果。

27.1 模拟算法核心概念​

核心思路：按部就班复现题目流程，不需要复杂数学推导，完全按照题目给出的规则、步骤编写代码，实时记录状态变化。 适用场景：题目给出清晰、分步执行的过程（游戏、排队、物理运动、计时、流程操作等）。

27.2 模拟算法标准实现步骤​

  1. 阅读理解完整流程，拆分每一步操作；
  2. 定义变量存储过程状态（时间、数量、位置、窗口空闲时间等）；
  3. 使用循环/分支复现每一步规则；
  4. 每次操作后更新状态变量；
  5. 满足终止条件后输出最终结果。

27.3 模拟算法优缺点​

优点​

  1. 逻辑和题目描述一一对应，易懂、好写；
  2. 无需复杂数学公式，新手友好；
  3. 只要读懂流程就能实现，适用范围极广。

缺点​

  1. 步骤极多时循环量大，运行效率偏低；
  2. 对文字细节敏感，漏一条规则就会结果错误；
  3. 大量状态记录会占用较多内存。

27.4 经典模拟代码示例​

示例1：模拟掷骰子10次，统计点数和为7的次数​

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
    srand(time(0)); // 设置随机种子
    int count7 = 0;
    for(int i = 0; i < 10; i++)
    {
        int d1 = rand() % 6 + 1;
        int d2 = rand() % 6 + 1;
        int sum = d1 + d2;
        printf("第%d次：%d+%d=%d\n", i+1, d1, d2, sum);
        if(sum == 7) count7++;
    }
    printf("点数之和等于7的次数：%d\n", count7);
    return 0;
}

示例2：银行多窗口排队模拟​

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
    srand(time(0));
    int windows[3] = {0}; // 记录3个窗口的空闲时刻
    int customer = 5;
    for(int i = 0; i < customer; i++)
    {
        int service = rand() % 5 + 1; // 服务时长1~5
        // 找到最早空闲窗口
        int minT = windows[0], idx = 0;
        for(int j = 1; j < 3; j++)
        {
            if(windows[j] < minT)
            {
                minT = windows[j];
                idx = j;
            }
        }
        int start = windows[idx];
        int end = start + service;
        windows[idx] = end;
        cout << "客户" << i+1 << "：窗口" << idx+1
             << "，开始：" << start << "，结束：" << end << endl;
    }
    return 0;
}

示例3：时钟秒针走动模拟（输出10秒）​

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
int main()
{
    int h = 12, m = 30, s = 0;
    for(int i = 0; i < 10; i++)
    {
        printf("%02d:%02d:%02d\n", h, m, s);
        this_thread::sleep_for(chrono::seconds(1));
        s++;
        if(s == 60)
        {
            s = 0;
            m++;
            if(m == 60)
            {
                m = 0;
                h++;
                if(h == 24) h = 0;
            }
        }
    }
    return 0;
}

示例4：小球下落反弹模拟​

题目：小球从10米落下，每次反弹高度为下落一半，模拟5次落地总路程、第5次反弹高度

#include <iostream>
using namespace std;
int main()
{
    double h = 10.0;
    double total = 0.0;
    int times = 5;
    for(int i = 0; i < times; i++)
    {
        total += h;
        if(i < times - 1)
        {
            h /= 2;
            total += h;
        }
    }
    cout << "第5次落地总路程：" << total << "米" << endl;
    cout << "第5次反弹高度：" << h / 2 << "米" << endl;
    return 0;
}

27.5 模拟编写注意事项​

  1. 逐字阅读题目规则，不漏任何限制条件；
  2. 状态变量初始化必须符合题目初始状态；
  3. 循环终止条件严格对应题目结束场景；
  4. 随机类模拟必须设置srand(time(0))保证随机不重复；
  5. 调试时打印中间状态，快速定位步骤逻辑错误。